package com.li.sort.arithmetic;

import java.util.Random;

/**
 * 快速选择排序平均时间复杂度为(O(n))
 * @author Administrator
 *
 */
public class QuickSelect {
	public static final int SIZE = 100000000;
	public static void main(String []args){
		int[] a = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			a[i] = random.nextInt(100);
		}
		a[10000]= 100;
		a[646464] = 100;
		//int a[]={2,20,3,7,9,1,17,18,0,4};
		int k=6;
		long startTime = System.currentTimeMillis();
		getTopKMinBySort(a,0,a.length-1,k);
		for(int i=0;i<k;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println("用时"+(System.currentTimeMillis()-startTime));
	}

	public static int partion(int a[],int first,int end){
		int i=first;
		int main=a[end];
		for(int j=first;j<end;j++){
			if(a[j]>main){
				int temp=a[j];
				a[j]=a[i];
				a[i]=temp;
				i++;
			}
		}
		a[end]=a[i];
		a[i]=main;
		return i;    
	}
	public static void getTopKMinBySort(int a[],int first,int end,int k){
		if(first<end){
			int partionIndex=partion(a,first,end);
			if(partionIndex==k-1)return;
			else if(partionIndex>k-1)getTopKMinBySort(a,first,partionIndex-1,k);
			else getTopKMinBySort(a,partionIndex+1,end,k);
		}
	}

}
